package algorithm.graph;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

//不能有负权值的边，如果存在负权值的边并且采用了负权值的边就会推翻之前的判断选择
public class Dijkstra {

    public static HashMap<Node, Integer> dijkstra1(Node from){
        HashMap<Node, Integer> unSelectNodes = new HashMap<>();
        HashMap<Node, Integer> selectNodes = new HashMap<>();
        unSelectNodes.put(from, 0);
        while(!unSelectNodes.isEmpty()){
            Node node = getMinDistanceAndUnselected(unSelectNodes);
            int weight = unSelectNodes.get(node);
            selectNodes.put(node, weight);
            unSelectNodes.remove(node);
            for (Edge edge : node.edges) {
                //有可能边的to端指回已经确定最小距离的点了，只会添加没有添加过的点，修改值更小的value值。（3种情况）
                if(!selectNodes.containsKey(edge.to) && (!unSelectNodes.containsKey(edge.to) || unSelectNodes.get(edge.to) > weight + edge.weight))
                    unSelectNodes.put(edge.to, edge.weight + weight);
            }
        }
        return selectNodes;
    }

    public static Node getMinDistanceAndUnselected(HashMap<Node, Integer> unSelectNodes){
        int min = Integer.MAX_VALUE;
        Node node = null;
        for (Map.Entry<Node, Integer> entry : unSelectNodes.entrySet()) {
            if(entry.getValue() < min){
                min = entry.getValue();
                node = entry.getKey();
            }
        }
        return node;
    }


    public static class NodeRecord{
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }


    public static class NodeHeap{
        public Node[] nodes;
        public HashMap<Node, Integer> heapIndexMap;
        public HashMap<Node, Integer> distanceMap;
        public int size;

        public NodeHeap(int size){
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            this.size = 0;
        }

        public boolean isEmpty(){
            return size == 0;
        }

        public void addOrUpdateOrOrIgnore(Node node, int weight){
            if(heapIndexMap.containsKey(node) && heapIndexMap.get(node) != -1){
                distanceMap.put(node, Math.min(weight, distanceMap.get(node)));
                insertHeapify(heapIndexMap.get(node));
            }
            if(!heapIndexMap.containsKey(node)){
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, weight);
                insertHeapify(size++);
            }
        }

        public NodeRecord pop(){
            Node node = nodes[0];
            NodeRecord nodeRecord = new NodeRecord(node, distanceMap.get(node));
            swap(0, size - 1);
            heapify(0, --size);
            heapIndexMap.put(node, -1);
            return nodeRecord;
        }

        private void insertHeapify(int index){
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1)/2])){
                swap(index, (index - 1)/2);
                index = (index - 1)/2;
            }
        }

        private void heapify(int index, int heapSize){
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            while(left < heapSize){
                int small = right < heapSize && distanceMap.get(nodes[right]) < distanceMap.get(nodes[left])? right : left;
                if(distanceMap.get(nodes[small]) < distanceMap.get(nodes[index])){
                    swap(small, index);
                    left = small * 2 + 1;
                    right = left + 1;
                    index = small;
                }else
                    break;
            }
        }

        private void swap(int index1, int index2){
            Node a = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = a;
            heapIndexMap.put(nodes[index1], index1);
            heapIndexMap.put(nodes[index2], index2);
        }


    }

    public static HashMap<Node, Integer> dijkstra2(Node from, int size){
        HashMap<Node, Integer> result = new HashMap<>();
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrOrIgnore(from, 0);
        while(!nodeHeap.isEmpty()){
            NodeRecord pop = nodeHeap.pop();
            result.put(pop.node, pop.distance);
            for (Edge edge : pop.node.edges) {
                nodeHeap.addOrUpdateOrOrIgnore(edge.to, pop.distance + edge.weight);
            }
        }
        return result;
    }





    public static void main(String[] args) {

        Integer[][] matrix ={{7, 0, 1}, {3, 1, 2}, {15, 0, 2}, {6, 2, 1}};
        Graph graph = GraphGenerator.createGraph(matrix);
        Node node = graph.nodes.get(0);
        HashMap<Node, Integer> map = dijkstra1(node);
        for (Map.Entry<Node, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey().value + ":" + entry.getValue());
        }
    }

}
